package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
最长递增子序列的长度
输入 4 2 3 1 5
输出 3 （因为 2 3 5组成了最长递增子序列）
in
5
4 2 3 1 5

out
3
 */
public class j最长递增子序列LISbyDPplus匪夷所思的优化 {
	public static void main(String[] args) {
		j最长递增子序列LISbyDPplus匪夷所思的优化 test = new j最长递增子序列LISbyDPplus匪夷所思的优化();
		test.useDP();
	}
	
	/**
	 * 前置方法
		|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	4


			|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	2
		^
		
				|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	2	3
			^
					|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	1	3
		^
		
						|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	1	3	5
				^

							|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	1	3	5	6
					^

								|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	1	3	4	6
				^
				
									|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	1	3	4	6	8
						^				
				
										|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	1	3	4	5	8
					^
				
											|
arr[]:	4	2	3	1	5	6	4	8	5	9
dp[]:	1	3	4	5	8	9
							^
	 */
	public void useDP() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = scanner.nextInt();
		}
		int[] dp = new int[N + 1];//因为dp的下标i的意义是当前截取的arr[]中的元素个数；所以我们不会使用到0,所以需要+1
		int res = DP(N, arr, dp);
		System.out.println(res);
	}
	
	/**
	 * O(NlogN)
	 * dp[i]的值，代表的是：长度=i的最长递增子序列的  末尾的  元素的值
	 * i在这里代表的是，当前截取的arr[]中的元素个数
	 * 这个算法是最经典的解决最长递增子序列问题
	 * 同时也是最烧脑的
	 * @param N
	 * @param arr
	 * @param dp
	 * @return
	 */
	public int DP(int N, int[] arr, int[] dp) {
		dp[1] = arr[0];//默认第一个dp元素是arr的首元素
		int lastUpdate = 1;//声明比dp中最后一个元素的索引；这个索引在数值意义上同时也是“历史最大递增子序列”的长度
		for (int index = 1; index < N; index++) {//遍历arr
			if (dp[lastUpdate] < arr[index]) {//当前index索引的arr元素A比dp中最后一个元素的数值大
				dp[lastUpdate + 1] = arr[index];//代表A可以存进“历史最大递增子序列”
				lastUpdate++;//同时更新dp中最后一个元素的索引
			} else {//不大，那么也要利用掉arr[index],不能浪费
				int indexOfFirstBiggerThan_arrIndex = findFirstBiggerThanX(dp, arr[index], 0, lastUpdate);//寻找dp中第一个大于arr[index]的元素B的索引
				if (indexOfFirstBiggerThan_arrIndex != -1) {//存在B
					dp[indexOfFirstBiggerThan_arrIndex] = arr[index];//替换B的数值
				}
			}
		}
		return lastUpdate;//返回历史最大递增子序列的长度
	}
	
	/**
	 * 在递增数组中，从左查找   第一个比X大的  元素的下标
	 * O(logN)
	 * 二分查找
	 * @param dp
	 * @param X
	 * @param start
	 * @param end
	 * @return
	 */
	public int findFirstBiggerThanX(int[] dp, int X, int start, int end) {
		while (start <= end) {
			int mid = (start + end) >>> 1;//在索引角度上的，中间值
			if (X < dp[mid]) {
				end = mid;
			} else {
				start = mid + 1;
			}
			if (start == end && X < dp[start]) {//start == end，也是while循环终止的条件；所以这条语句只可能执行一次
				return start;
			}
		}
		return -1;//就代表当前的dp片段中，没有比X大的
	}
}
